package com.xinheyun.demo.leetcode;

import java.util.Arrays;

/**
 * @description: TODO
 * @author: Sarah
 * @modified By: Sarah
 * @date: Created in 2021/8/31 12:14
 * @version:v1.0
 */
//给你一个整数数组 nums 和一个整数 target 。
//
//    向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：
//
//    例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。
//    返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。
//
//     
//
//    示例 1：
//
//    来源：力扣（LeetCode）
//    链接：https://leetcode-cn.com/problems/target-sum
//    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
public class test494 {

    public static void main(String[] args) {
        int[] ints = {-100};
        test494 test494 = new test494();
        System.out.println(test494.findTargetSumWays(ints, 200));

    }
    public int findTargetSumWays(int[] nums, int target) {
        int sum = Arrays.stream(nums).sum();
        if((target+sum)%2==1 && (target+sum)<0){
            return 0;
        }
        int end = (target+sum)/2;
        int[] dp = new int[end+1];
        dp[0]=1;
        for(int num:nums){
            for(int i = end;i>=num;i--){
                dp[i]+=dp[i-num];
            }
        }
        return dp[end];
    }
}
